package leetcode_1401_1500;

import java.util.Arrays;

public class LeeCode_1439 {
    public static void main(String[] args) {
        System.out.println(kthSmallest(new int[][]{{1, 3, 11}, {2, 4, 6}}, 5));
    }
    private static int kthSmallest(int[][] mat, int k){
        int[] a = new int[]{0};
        for (int[] row : mat) {
            int[] b = new int[a.length * row.length];
            int i = 0;
            for (int n1 : a) {
                for (int n2 : row) {
                    b[i++] = n1 + n2;
                }
            }
            Arrays.sort(b);
            if (b.length > k){
                b = Arrays.copyOfRange(b, 0, k);
            }
            a = b;
        }
        return a[k - 1];
    }
}
